
public class Leetcode70 {
    public static void main(String[] args) {
        System.out.println(climbStairs(45));
    }

    private static int[] k = {0, 1, 2, 3, 5, 8};

    public static int climbStairs(int n) {
        if (n <= 5) {
            return k[n];
        }

        return climbStairs(n - 1) + climbStairs(n - 2);
    }
}
